package 力扣算法练习.main1.part2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class day23 {
     static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /*
    给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
    https://leetcode.cn/problems/rotate-list/
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head==null||head.next==null)return head;
        ListNode cur=head;
        LinkedList<ListNode> temp=new LinkedList<>();
        int count=0;//统计有多少个元素
        while(cur!=null){
            temp.addLast(cur);
            cur=cur.next;
            count++;
        }
        k=k%count;
        while(k>0){
            temp.addFirst(temp.removeLast());
            k--;
        }
        head=temp.getFirst();
        temp.removeFirst();
        cur=head;
        while(!temp.isEmpty()){
            cur.next=temp.removeFirst();
            cur=cur.next;
        }
        cur.next=null;
        return head;
    }
    //官方解
    public ListNode rotateRight1(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter.next = head;
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;
        iter.next = null;
        return ret;
    }
}
